import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2022-11-21
 * Time: 22:11
 */
public class TaskOfDS_BinaryTree {
    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {

        }
        TreeNode(char val) {
            this.val = val;
        }
    }

    // 先序创建二叉树
    private int CTPreO = 0;
    public TreeNode createTreePreOrder(String s) {
        TreeNode root = null;
        if (s.charAt(CTPreO) != '#') {
            root = new TreeNode(s.charAt(CTPreO));
            CTPreO++;
            root.left = createTreePreOrder(s);
            root.right = createTreePreOrder(s);
        } else {
            CTPreO++;
        }
        return root;
    }

    // 层序创建二叉树
    public TreeNode createTreeLevelOrder(String s) {
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode childNode = null;
        TreeNode node = null;
        node = new TreeNode(s.charAt(0));
        queue.offer(node);
        index++;
        while(!queue.isEmpty()) {
            childNode = queue.poll();
            if(s.charAt(index) != '#') {
                childNode.left = new TreeNode();
                childNode.left.val = s.charAt(index);
                queue.add(childNode.left);
            }
            index++;
            if(s.charAt(index) != '#') {
                childNode.right = new TreeNode();
                childNode.right.val = s.charAt(index);
                queue.add(childNode.right);
            }
            index++;
        }
        return node;
    }

    // 先序遍历二叉树(递归)
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历二叉树(递归)
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    // 后序遍历二叉树(递归)
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    // 先序遍历二叉树(非递归)
    public void preorderTraversalNor(TreeNode root) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    // 中序遍历二叉树(非递归)
    public void inorderTraversalNor(TreeNode root) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    // 后序遍历二叉树(非递归)
    public void postorderTraversalNor(TreeNode root) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null
                    || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
    }

    // 层序遍历
    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()) {
            TreeNode cur = qu.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                qu.offer(cur.left);
            }
            if(cur.right != null) {
                qu.offer(cur.right);
            }
        }
    }

    // 求树中节点个数
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }

    // 度为1的节点个数
    public int getDegreeIs1(TreeNode root){
        if(root.left!=null&&root.right!=null)	//若某节点左右孩子都不为空，
            return getDegreeIs1(root.left)+getDegreeIs1(root.right);	//则该结点下的度为1的结点为左右孩子的之和
        else if(root.left==null&&root.right!=null)
            return 1+getDegreeIs1(root.right);
        else if(root.left!=null&&root.right==null)
            return 1+getDegreeIs1(root.left);
        return 0;
    }

    // 度为2的节点个数
    public int getDegreeIs2(TreeNode root){
        return size(root) - getLeafNodeCount(root);
    }

    // 获取二叉树深度
    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    // 交换左右子树
    public void swap(TreeNode root) {
        if (root != null) {
            TreeNode cur = root.left;
            root.left = root.right;
            root.right = cur;
            swap(root.left);
            swap(root.right);
        }
    }
}
